/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package fr.univnantes.alma.arbres;

import java.util.Vector;
import java.util.Iterator;
import fr.univnantes.alma.arbres.exceptions.PereRacineException;
import fr.univnantes.alma.arbres.exceptions.PlaceIndisponibleException;


/**
 * Cette classe numérote les étiquettes de la façon suivante :
 * La racine est numérotée 0, chaque nouveau nœud ajouté a un numéro
 * immédiatement supérieur au nœud ajouté juste avant.
 *
 * Les fils d’un nœud sont numérotés à partir de 1.
 * @author judu
 */
public class ArbreTM<T> implements Arbre<T>, Iterable<Noeud<T>> {


    private Vector<NoeudTM<T>> arbre;
    /**
     * etiquette représente l’étiquette utilisée lors de la prochaine insertion.
     */
    private Integer etiquette = new Integer(-1);
    private Integer arite;

    /**
     * L’étiquette de la racine est toujours 0
     */
    public ArbreTM(int arite) {
        this.arbre = new Vector<NoeudTM<T>>();
        this.arite = arite;
        this.arbre.add(0, this.createFils(0,1));
    }


    private NoeudTM<T>  createFils(int index, int pos){
        ++this.etiquette;
        return new NoeudTM<T> (this.etiquette, index, pos);
    }

    private int indexFromPos(int indexPere, int pos){
        return indexPere*this.arite + pos;
    }

    private Boolean positionAutorisee(int pos){
        return (pos > 0 && pos <= this.arite);
    }

    private NoeudTM<T>  castNoeud(Noeud<T> n){
        return (NoeudTM<T> ) n;
    }

    /**
     * Cette fonction agrandit le tableau à chaque fois qu'on le dépasse.
     * La nouvelle taille permet d'insérer {arite} fils au noeud d'index {index}
     * @param index
     */
    private void ensureIndex(int index){
        if (this.arbre.size() <= index){
            this.arbre.setSize((index+1)*this.arite+1);
        }
        
    }
    /**
     * Un fils est ajouté dans la première case libre.
     * @param pere
     * @return
     */
    public Noeud<T> ajoutFils(Noeud<T> pere) throws PlaceIndisponibleException, NullPointerException {
        NoeudTM<T>  tmp = (pere != null)? this.castNoeud(pere):null;
        if (tmp == null) throw new NullPointerException("On ne peut pas ajouter un fils à un noeud null");

        int indexPere = tmp.getIndex();

        //On s'assure que le nouveau noeud pourra bien être inséré dans le Vector
        this.ensureIndex((indexPere+1)*this.arite);
        
        int i=1;
        while(this.arbre.get(indexPere*this.arite + i) != null && i <= this.arite){
            ++i;
        }
        
        if(i > this.arite){
            throw new PlaceIndisponibleException("L’arité a été atteinte pour le nœud d’étiquette "+tmp.getEtiquette().toString()+". Il ne peut pas avoir plus de fils.");
        } else {

            int index = indexPere*this.arite + i;
            NoeudTM<T> fils = this.createFils(index, i);
            this.arbre.set(index, fils);
            return (fils.autoCast());
        }
    }


    public Noeud<T> ajoutFils(Noeud<T> pere, T valeur) throws PlaceIndisponibleException, NullPointerException {
        if(valeur == null){
            return this.ajoutFils(pere);
        } else {
            Noeud<T> tmp = this.ajoutFils(pere);
            tmp.setValeur(valeur);
            return tmp;
        }
    }


    public Noeud<T> ajoutFilsEnPos(Noeud<T> pere, int pos) throws PlaceIndisponibleException, NullPointerException {
        NoeudTM<T>  tmp = (pere != null)? this.castNoeud(pere):null;
        if (tmp == null) throw new NullPointerException("On ne peut pas ajouter un fils à un noeud null");
        
        int index = tmp.getIndex()*this.arite + pos;

        this.ensureIndex((tmp.getIndex()+1)*this.arite);

        if(!this.positionAutorisee(pos)) throw new PlaceIndisponibleException("On ne peut ajouter un fils en position "+Integer.toString(pos));
        if(this.arbre.get(index) != null) throw new PlaceIndisponibleException("Place déjà occupée");
        
        NoeudTM<T>  fils = this.createFils(index, pos);
        this.arbre.set(index,fils);
        return fils;
    }

    public Noeud<T> ajoutFilsEnPos(Noeud<T> pere, int pos, T valeur) throws PlaceIndisponibleException, NullPointerException {
        if(valeur == null){
            return this.ajoutFilsEnPos(pere,pos);
        } else {
            Noeud<T> tmp = this.ajoutFilsEnPos(pere,pos);
            tmp.setValeur(valeur);
            return tmp;
        }
    }
    
    public Noeud<T> getRacine() {
        return this.arbre.get(0);
    }

    public Noeud<T> getNoeudByEtiquette(int etiquette) throws NullPointerException {

        if (etiquette < 0) throw new NullPointerException("On a dit « Pas d'étiquette négative » !");

        Iterator<NoeudTM<T>> iterator = arbre.iterator();
        Boolean nonTrouve = true;
        NoeudTM<T>  current = null;

        while (iterator.hasNext() && nonTrouve){
            current = iterator.next();
            nonTrouve = current.getEtiquette() != etiquette;
        }
        if (!nonTrouve){
            return current.autoCast();
        }

        return null;
    }

    
    public Noeud<T> getFilsByPos(Noeud<T> pere, int pos) throws PlaceIndisponibleException, NullPointerException {

        NoeudTM<T>  tmp = (pere != null)? this.castNoeud(pere):null;
        if (tmp == null) throw new NullPointerException("On ne peut pas récupérer le fils d'un noeud null");


        if(!this.positionAutorisee(pos)) throw new PlaceIndisponibleException("La position "+Integer.toString(pos)+" n’est pas autorisée.");

        int index = this.indexFromPos(tmp.getIndex(), pos);

        if(index >= this.arbre.size()) return null;
        else return this.arbre.get(index);
    }

    public Noeud<T> getPere(Noeud<T> fils) throws PereRacineException, NullPointerException {
        NoeudTM<T>  tmp = (fils != null)? this.castNoeud(fils):null;
        if (tmp == null) throw new NullPointerException("Un noeud null n'a pas de pere");

        if(this.isRacine(fils)) throw new PereRacineException("On ne peut pas récupérer le père de la racine.");

        int indexPere = (tmp.getIndex() - tmp.getPosition())/this.arite;

        return this.arbre.get(indexPere).autoCast();
    }

    public int getPosition(Noeud<T> noeud) throws NullPointerException {
        NoeudTM<T>  tmp = (noeud != null)? this.castNoeud(noeud):null;
        if (tmp == null) throw new NullPointerException("Un Noeud<T> null n'a pas de position");
        return tmp.getPosition();
    }

    public Noeud<T> getNextFrere(Noeud<T> noeud) throws NullPointerException {
        NoeudTM<T>  tmp = (noeud != null)? this.castNoeud(noeud):null;
        if (tmp == null) throw new NullPointerException("Un noeud null n'a pas de frère");

        //si c'est la racine, pas de frère
        if(this.isRacine(tmp)) return null;

        int in = tmp.getIndex()+1;
        int po = tmp.getPosition()+1;
        while(po <= arite && this.arbre.get(in) == null){
            ++po;
            ++in;
        }
        if(po > arite) {
            return null;
        }else{
            return this.arbre.get(in).autoCast();
        }
        
    }

    public Noeud<T> getPreviousFrere(Noeud<T> noeud) throws NullPointerException {
        NoeudTM<T>  tmp = (noeud != null)? this.castNoeud(noeud):null;
        if (tmp == null) throw new NullPointerException("Un noeud null n'a pas de frère");

        //si c'est la racine, pas de frère.
        if(this.isRacine(tmp)) return null;
        
        int in = tmp.getIndex()-1;
        int po = tmp.getPosition()-1;
        while(po > 0 && this.arbre.get(in) == null){
            --po;
            --in;
        }
        if(po==0) {
            return null;
        }else{
            return this.arbre.get(in).autoCast();
        }
    }

    public Noeud<T> getFirstFils(Noeud<T> noeud){
        NoeudTM<T>  tmp = (noeud != null)? this.castNoeud(noeud):null;
        if (tmp == null) throw new NullPointerException("Un noeud null n'a pas de fils");

        int po = 1;
        int in = this.indexFromPos(tmp.getIndex(), po);
        while(po <= arite && in < this.arbre.size() && this.arbre.get(in) == null){
            ++po;
            ++in;
        }
        if(po > arite || in >= this.arbre.size()) {
            return null;
        }else{
            return this.arbre.get(in).autoCast();
        }
    }

    public Boolean isRacine(Noeud<T> noeud) {
        NoeudTM<T>  tmp = (noeud != null)? this.castNoeud(noeud):null;
        if (tmp == null) throw new NullPointerException("Le noeud est null, donc à priori ce n'est pas la racine");
        return tmp.getIndex() == 0;
    }


     public Boolean hasNextFrere(Noeud<T> noeud) throws NullPointerException {
       return (this.getNextFrere(noeud) != null);
    }

    public Boolean hasPreviousFrere(Noeud<T> noeud) throws NullPointerException {
        return (this.getPreviousFrere(noeud) != null);
    }

    public Boolean hasFils(Noeud<T> noeud) throws NullPointerException {
        return (this.getFirstFils(noeud) != null);
    }


    private void nettoieArbre() {
        if (this.arbre.size() > 0){
            int i = this.arbre.size() -1;
            while (i > 0 && this.arbre.get(i) == null) --i;
            if (this.arbre.get(i) != null) this.arbre.setSize((i+1)*this.arite+1);


        }
        
    }

    private Noeud<T> nextNonFils(NoeudTM<T> noeud){
        if(hasNextFrere(noeud)) {
            return this.getNextFrere(noeud);
        } else {
            NoeudTM<T> tmp;
            try {
                tmp = (NoeudTM<T>) getPere(noeud);
            } catch (PereRacineException ex) {
                return null;
            }
            while(!hasNextFrere(tmp)){
                try {
                    tmp = (NoeudTM<T>) getPere(tmp);
                } catch (PereRacineException ex) {
                    return null;
                }
            }
            return getNextFrere(tmp);
        }
    }

    @SuppressWarnings("empty-statement")
    public void deleteFils(Noeud<T> noeud) throws NullPointerException {
                /* Vérifications */
        if(noeud == null) throw new  NullPointerException();
        if(noeud.getEtiquette() > this.etiquette || noeud.getEtiquette() < 0) throw new NullPointerException("Le noeud n'appartient pas à l'arbre.");

        /* On cast */
        NoeudTM<T> temp = this.castNoeud(noeud);

        /* On supprime les fils, sous fils et le noeud */

        if(this.hasFils(temp)){
            NoeudTM<T> n = (NoeudTM<T>) this.getFirstFils(temp);
            while(this.hasNextFrere(n)){
                this.deleteFils(n);
                this.arbre.set(n.getIndex(), null);
                n = (NoeudTM<T>) this.getNextFrere(n);
            }
            // On a le dernier, qui n'a plus de Frère
            this.deleteFils(n);
            this.arbre.set(n.getIndex(), null);
        }
        this.nettoieArbre();
    }

    @SuppressWarnings("empty-statement")
    public void deleteNoeud(Noeud<T> noeud) throws NullPointerException {
        if(noeud == null) throw new  NullPointerException();
        if(noeud.getEtiquette() > this.etiquette || noeud.getEtiquette() < 0) throw new NullPointerException("Le noeud n'appartient pas à l'arbre.");

        /* On cast */
        NoeudTM<T> temp = this.castNoeud(noeud);

        this.deleteFils(noeud);
        this.arbre.set(temp.getIndex(), null);

    }



    /************* ITERATOR *************/
    public Iterator<Noeud<T>> iterator() {
        return new ArbreTMIteratorBFS<T>(this.arbre);
    }

    public Iterator<Noeud<T>> iteratorBFS() {
        return new ArbreTMIteratorBFS<T>(this.arbre);
    }

    public Iterator<Noeud<T>> iteratorDFS() {
        return new ArbreTMIteratorDFS<T>(this.arbre, this.arite);
    }
    
    public Iterator<Noeud<T>> iterator(ArbreIteratorType typeIt) {

        switch(typeIt){
            case DFS:
                return this.iteratorDFS();
            case BFS:
                return this.iteratorBFS();
            default:
                return this.iterator();
        }
    }




    /*********** AFFICHAGE **************/
    /******** Fonctions obsolètes *******/
    public void affichageListeAdj(){
        Iterator<NoeudTM<T>> it = this.arbre.iterator();
        while(it.hasNext()){
            NoeudTM<T>  n = it.next();
            if(n != null){
                System.out.println(n + " a pour fils : ");
                System.out.print("  [");
                int indPere = n.getIndex();
                for(int i = indPere*this.arite+1; i < arbre.size() && i < (indPere+1)*this.arite; ++i){
                    if(this.arbre.get(i) != null){
                        System.out.print(this.arbre.get(i)+", ");
                    }
                }

                if((indPere+1)*this.arite < this.arbre.size() && this.arbre.get((indPere+1)*this.arite) != null){
                    System.out.println(this.arbre.get((indPere+1)*this.arite)+"]");
                } else {
                    System.out.println("]");
                }
            }
        }
    }



    public void affichageNoeudArc(){
        System.out.println("Liste des Noeuds :");
        System.out.print("  ");
        this.afficheNoeuds();
        System.out.println("Liste des arcs :");
        System.out.print("  ");
        this.afficheArcs();

    }

    private void afficheNoeuds(){
        Iterator<NoeudTM<T>> it = this.arbre.iterator();

        while(it.hasNext()){
            Noeud<T> n = it.next();
            if(n != null){
                System.out.print(n+" ");
            }
        }
        System.out.println();
    }

    private void afficheArcs() {
        Iterator<NoeudTM<T>> it = this.arbre.iterator();

        while(it.hasNext()){
            NoeudTM<T> n = it.next();
            if (n != null){
                this.printLesArcsDuNoeud(n);
            }
        }
        System.out.println();
    }


        private void printLesArcsDuNoeud(NoeudTM<T> n){
        int posFils = n.getIndex()*this.arite;

        if(!this.hasFils(n)) return;

        for(int i=posFils+1; i <= posFils+this.arite; ++i){

            NoeudTM<T> fils = this.arbre.get(i);

            if(fils != null){
                this.printArc(n, fils);
                System.out.print(" ");
            }
        }
    }

    private void printArc(NoeudTM<T> n, NoeudTM<T> fils) {
            System.out.print("("+n.getEtiquette()+", "+fils.getEtiquette()+")");
    }





}
